import java.util.*;
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Solution133 {
    public void DFSclone(Node node,Node newNode,Map<Node,Node> nodeMark){
        for (Node tmpNode:node.neighbors) {
            Node tmpNewNode;
            if(nodeMark.containsKey(tmpNode)==false) {
                tmpNewNode = new Node(tmpNode.val);
                newNode.neighbors.add(tmpNewNode);
                nodeMark.put(tmpNode,tmpNewNode);
                DFSclone(tmpNode, tmpNewNode, nodeMark);
            }
            else{
                tmpNewNode=nodeMark.get(tmpNode);
                newNode.neighbors.add(tmpNewNode);
            }
        }
    }

    public Node cloneGraph(Node node) {
        if(node==null){
            return null;
        }
        Node newRoot=new Node(node.val);
        Map<Node,Node> nodeMark=new HashMap<>();
        nodeMark.put(node,newRoot);
        DFSclone(node,newRoot,nodeMark);
        return newRoot;
    }
}
